So now the point is, given an arbitrary constraint network, how do I get to an A-cyclic graph?

And the answer in general is I can't.

Like, given any kind of, I mean, this whole example with Australia is already, it's a

cyclic graph, so I can't make a cyclic graph non-cyclic, except if I get rid of constraints

and that's exactly what I don't want to do.

If I get rid of constraints, then either I'm adding solutions that aren't solutions

or I'm just making my algorithm more inefficient.

So the idea is to introduce this notion of a cut set.

Where a cut set is basically just any subset of my set of variables,

such that if I get rid of all those variables, the resulting graph will be acyclic.

And of course, that means, given an arbitrary constraint graph,

there is lots of potential cut sets.

So the question is, which cut sets are the ones that are most desirable?

So looking at this graph, basically every subset of this that contains whatever this yellow node is,

again, which one is missing?

South Australia? Is that right?

So every subset of my variables that contain South Australia will be a cut set.

If I get rid of any of those, the resulting node will be acyclic.

So the question is, which cut sets are the ones that I want to use?

Ideally.

Or let me rephrase the question. I can get rid of South Australia.

That makes sense. I can also get rid of South Australia and Queens and New South Wales.

Why is that not that good an idea?

Or why is it not a better idea than just getting rid of South Australia?

Yes?

Because getting rid of South Australia is already enough to get an acyclic graph?

Yes, exactly. Once I get rid of this one node, I have an acyclic graph,

and I can do this whole thing with this algorithm, which is quick.

If I first get rid of South Australia and then get rid of another node with the same algorithm,

and only then I start treating it as an acyclic graph,

then I'm just doing one step which I wouldn't have had to do if I stopped immediately after South Australia.

So the idea is we want to find a cut set, and we want this cut set to be as small as possible.

So that we know once I've assigned the variables in the cut set,

I can start treating the rest of the thing as an acyclic graph.

So here's the idea. I do backtracking on the graph, and I assign those variables first that form a cut set.

And once I've assigned all the values of the cut set, I get an acyclic constraint graph,

and then I use the algorithm from the section before to use the remaining problem.

So here's how this works with respect to cut set conditioning.

This is just the algorithm for the acyclic graph.

Basically wrapped in a usual constraint satisfaction solving algorithm.

I basically just research with the additional idea that I take the set V0,

where V0 is just any kind of cut set of my set of variables V.

I do the usual thing. I do a forward checking. I assign the variables.

And this is the usual stuff.

So in particular here, if there isn't, this is the else thing,

if I don't have a variable in my cut set that isn't already defined in my partial assignment,

then I can go over to the acyclic thing.

And then just return inconsistent for a solution.

And before that, I just do the usual stuff.

I basically recurse and do research.